Backspace string compare

Time: O(M+N); Space: O(1); easy

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: S = “ab#c”, T = “ad#c”

Output: True

Explanation:

  • Both S and T become “ac”.

Example 2:

Input: S = “ab##”, T = “c#d#”

Output: True

Explanation:

  • Both S and T become “”.

Example 3:

Input: S = “a##c”, T = “#a#c”

Output: True

Explanation:

  • Both S and T become “c”.

Example 4:

Input: S = “a#c”, T = “b”

Output: False

Explanation:

  • S becomes “c” while T becomes “b”.

Constraints:

  • 1 <= S.length <= 200

  • 1 <= T.length <= 200

  • S and T only contain lowercase letters and ‘#’ characters.

Follow up:

  • Can you solve it in O(N) time and O(1) space?

1. Two Pointer [O(M+N), O(1)]

Intuition

When writing a character, it may or may not be part of the final string depending on how many backspace keystrokes occur in the future.

If instead we iterate through the string in reverse, then we will know how many backspace characters we have seen, and therefore whether the result includes our character.

Algorithm

Iterate through the string in reverse. If we see a backspace character, the next non-backspace character is skipped. If a character isn’t skipped, it is part of the final answer.

[3]:

class Solution1(object):
    """
    Time: O(M+N)
    Space: O(1)
    """
    def backspaceCompare(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        def findNextChar(S):
            skip = 0
            for i in reversed(range(len(S))):
                if S[i] == '#':
                    skip += 1
                elif skip:
                    skip -= 1
                else:
                    yield S[i]

        return all(x == y for x, y in zip(findNextChar(S), findNextChar(T)))

[4]:

s = Solution1()

S = "ab#c"
T = "ad#c"
assert s.backspaceCompare(S, T) ==  True

S = "ab##"
T = "c#d#"
assert s.backspaceCompare(S, T) == True

S = "a##c"
T = "#a#c"
assert s.backspaceCompare(S, T) ==  True

S = "a#c"
T = "b"
assert s.backspaceCompare(S, T) == False

2. Build String [O(M+N), O(M+N)]

Intuition

Let’s individually build the result of each string (build(S) and build(T)), then compare if they are equal.

Algorithm

To build the result of a string build(S), we’ll use a stack based approach, simulating the result of each keystroke.

[5]:

class Solution2(object):
    """
    Time: O(M+N)
    Space: O(M+N)
    """
    def backspaceCompare(self, S, T):

        def build(S):
            res = []
            for c in S:
                if c != '#':
                    res.append(c)
                elif res:
                    res.pop()
            return "".join(res)

        return build(S) == build(T)

[6]:

s = Solution2()

S = "ab#c"
T = "ad#c"
assert s.backspaceCompare(S, T) ==  True

S = "ab##"
T = "c#d#"
assert s.backspaceCompare(S, T) == True

S = "a##c"
T = "#a#c"
assert s.backspaceCompare(S, T) ==  True

S = "a#c"
T = "b"
assert s.backspaceCompare(S, T) == False